package com.zhang.study.chapter06;

import java.util.PriorityQueue;

/**
 * 2208. 将数组和减半的最少操作次数
 * <a href="https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/">...</a>
 */
public class Code06_HalveArray {

    public int halveArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        PriorityQueue<Double> heap = new PriorityQueue<>((o1, o2) -> (int) (o2 - o1));
        double sum = 0;
        for (int num : nums) {
            sum += num;
            heap.add((double) num);
        }
        int count = 0;
        double curSum = 0;
        while (curSum < sum / 2 && !heap.isEmpty()) {
            double poll = heap.poll() / 2;
            curSum += poll;
            heap.add(poll);
            count++;
        }
        return count;
    }


    // 手动实现一个堆结构
    public static int MAX = 100001;

    public static long[] heap = new long[MAX];

    public static int size;


    public static int halveArray2(int[] nums) {
        size = nums.length;
        long sum = 0;
        for (int i = size - 1; i >= 0; i--) {
            heap[i] = (long) nums[i] << 20;
            sum += heap[i];
            heapify(i);
        }
        sum/=2;
        int count = 0;
        double curSum = 0;
        while (curSum < sum ) {
            heap[0] /= 2;
            curSum += heap[0];
            count++;
            heapify(0);
        }
        return count;
    }

    public static void heapify(int index) {
        int left = (index << 1) + 1;
        while (left < size) {
            int largest = left + 1 < size && heap[left + 1] > heap[left] ? left + 1 : left;
            largest = heap[largest] > heap[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(largest, index);
            index = largest;
            left = (index << 1) + 1;
        }
    }

    public static void swap(int i, int j) {
        long tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }


}
